package com.zs.letcode.illustration_of_algorithm;

/**
 * 剑指 Offer 64. 求 1 + 2 + … + n
 * 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入: n = 3
 * 输出:6
 * 示例 2：
 * <p>
 * 输入: n = 9
 * 输出:45
 *
 * <p>
 * 限制：
 * <p>
 * 1 <= n<= 10000
 * 相关标签
 * 位运算
 * 递归
 * 脑筋急转弯
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9h44cj/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/19 08:22
 */
public class Chapter37 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.sumNums2(9));
    }

    private static class Solution {
        /**
         * 方法一： 平均计算
         * 问题： 此计算必须使用 乘除法 ，因此本方法不可取，直接排除。
         */
        public int sumNums(int n) {
            return (1 + n) * n / 2;
        }

        /**
         * 方法二： 迭代
         * 问题： 循环必须使用 while 或 for ，因此本方法不可取，直接排除。
         */
        public int sumNums1(int n) {
            int res = 0;
            for (int i = 1; i <= n; i++) {
                res += i;
            }
            return res;
        }

        /**
         * 方法三： 递归
         * 问题： 终止条件需要使用 if ，因此本方法不可取。
         * 思考： 除了 if 和 switch 等判断语句外，是否有其他方法可用来终止递归？
         */
        public int sumNums2(int n) {
            if (n == 1) {
                return 1;
            }
            n += sumNums2(n - 1);
            return n;
        }

        int res = 0;

        public int sumNums3(int n) {
            boolean x = n > 1 && sumNums3(n - 1) > 1;
            res += n;
            return res;
        }

        public int sumNums4(int n) {
            boolean x = n > 1 && (n += sumNums4(n - 1)) > 0;
            return n;
        }

        /**
         * 方法二：快速乘
         */
        public int sumNums5(int n) {
            int ans = 0, A = n, B = n + 1;
            boolean flag;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            flag = ((B & 1) > 0) && (ans += A) > 0;
            A <<= 1;
            B >>= 1;

            return ans >> 1;
        }
    }
}
